Twitter搜索是如何设计的？
在互联网增长速度趋于稳定的今天，许多大厂已将面试重心从八股文转向场景题，也就是系统设计，强调应聘者在实际工作环境中的解决问题能力。这就是我推出的系统设计系列的初衷，专注于系统设计的深度学习和面试技巧。在这个系列中，提供大量真实的系统设计场景题，以及高效的解决方案。无论您是初学者还是资深从业者，都能在这里得到宝贵的知识和经验。点击关注
Twitter是最大的社交网络服务之一，用户可以分享照片、新闻和文字消息。在本章中，我们将设计一个可以存储和搜索用户推文的服务。
相似问题：推文搜索。
难度级别：中等
1. 什么是Twitter搜索？
Twitter用户可以随时更新他们的状态。每个状态（称为推文）都由纯文本组成，我们的目标是设计一个能够搜索所有用户推文的系统。
2. 系统的要求和目标
• 让我们假设Twitter有15亿的总用户，其中每天有8亿的活跃用户。
• Twitter每天平均收到4亿条推文。
• 一条推文的平均大小为300字节。
• 我们假设每天将有5亿次搜索。
• 搜索查询将由多个词组成，并用AND/OR连接。
我们需要设计一个可以高效存储和查询推文的系统。
3. 容量估计和限制
存储容量：由于我们每天有4亿条新推文，每条推文平均为300字节，我们需要的总存储空间将是：
400M * 300 => 120GB/天每秒总存储量：
120GB / 24小时 / 3600秒 ~= 1.38MB/秒4. 系统API
我们可以有SOAP或REST API来暴露我们服务的功能；以下是搜索API的定义：
参数：api_dev_key（字符串）：注册账户的API开发者密钥。这将被用于根据他们分配的配额对用户进行节流等操作。search_terms（字符串）：包含搜索词的字符串。maximum_results_to_return（数字）：返回的推文数量。sort（数字）：可选的排序方式：最新的优先（0 - 默认），最匹配的（1），最受欢迎的（2）。page_token（字符串）：此令牌将指定应返回结果集中的某一页。
返回：（JSON） 一个包含匹配搜索查询的推文列表信息的JSON。每个结果条目可以有用户ID和姓名，推文文本，推文ID，创建时间，点赞数等。
5. 高级设计
在高级别上，我们需要将所有状态存储在数据库中，并且构建一个索引，该索引可以跟踪哪个词出现在哪个推文中。这个索引将帮助我们快速找到用户试图搜索的推文。
6. 细节组件设计
1. 存储：我们需要每天存储120GB的新数据。鉴于这大量的数据，我们需要提出一个数据分区方案，该方案能有效地将数据分配到多个服务器上。如果我们为接下来的五年做计划，我们将需要以下的存储空间：
120GB * 365天 * 5年 ~= 200TB如果我们不希望任何时候都超过80%的满载，我们大约需要250TB的总存储空间。假设我们想保留所有推文的额外副本以实现容错；那么，我们的总存储需求将为500TB。如果我们假设一个现代服务器可以存储最多4TB的数据，那么我们需要125台这样的服务器来存储接下来五年所需的所有数据。
让我们从简单的设计开始，我们将推文存储在MySQL数据库中。我们假设我们将推文存储在一个有两列的表中，TweetID(推文ID)和TweetText(推文文本)。我们假设我们根据TweetID对数据进行分区。如果我们的TweetIDs在整个系统中是唯一的，我们可以定义一个哈希函数，该函数可以将TweetID映射到一个存储服务器，我们可以在那里存储推文对象。
如何创建系统范围内唯一的TweetIDs？如果我们每天获得4亿新推文，那么五年后我们可以预计会有多少推文对象？
400M * 365天 * 5年 => 7300亿这意味着我们需要一个五字节的数字来唯一识别TweetIDs。假设我们有一个服务，当我们需要存储一个对象时，可以生成一个唯一的TweetID（这里讨论的TweetID将类似于在设计Twitter中讨论的TweetID）。我们可以将TweetID输入到我们的哈希函数中，找到存储服务器并将推文对象存储在那里。
1. 索引：我们的索引应该是什么样的？因为我们的推文查询将由单词组成，让我们构建一个索引，它可以告诉我们哪个单词在哪个推文对象中出现。首先，让我们估计一下我们的索引会有多大。如果我们想为所有的英语单词和一些著名的名词，比如人名、城市名等建立索引，如果我们假设我们有大约300K英语单词和200K名词，那么我们的索引将有500k个总词。假设一个单词的平均长度为五个字符。如果我们在内存中保存我们的索引，我们需要2.5MB的内存来存储所有的单词：
500K * 5 => 2.5 MB假设我们只想将过去两年的所有推文的索引保留在内存中。由于我们在5年内将获得7300亿条推文，这将给我们带来2920亿条推文。给定每个TweetID将是5字节，存储所有的TweetIDs需要多少内存？2920亿 * 5 => 1460 GB因此，我们的索引将像一个大型的分布式哈希表，其中'key'将是单词，'value'将是包含该单词的所有推文的TweetIDs的列表。假设每条推文平均有40个单词，因为我们不会对介词和其他小词，如'the'、'an'、'and'等进行索引，让我们假设每条推文中需要索引的单词大约有15个。这意味着每个TweetID将在我们的索引中存储15次。因此，我们需要的总内存来存储我们的索引：(1460 * 15) + 2.5MB ~= 21 TB假设一个高端服务器有144GB的内存，我们将需要152台这样的服务器来存储我们的索引。
我们可以根据两个标准来对数据进行分片：基于单词的分片：在构建我们的索引时，我们将遍历推文的所有单词，并计算每个单词的哈希值，以找到它应该被索引的服务器。为了找到包含特定单词的所有推文，我们只需要查询包含这个单词的服务器。
这种方法有一些问题：
1. 如果一个单词变得热门怎么办？那么存储该词的服务器上会有大量的查询。这种高负载将影响我们服务的性能。
2. 随着时间的推移，一些词可能会存储比其他词更多的TweetIDs，因此，在推文增长的同时，保持词的均匀分布是相当棘手的。
为了从这些情况中恢复，我们要么需要重新划分我们的数据，要么使用一致性哈希(Consistent Hashing)。基于推文对象的分片：在存储时，我们将TweetID传递给我们的哈希函数，以找到服务器并在该服务器上索引推文的所有单词。在查询特定单词时，我们必须查询所有的服务器，每个服务器将返回一组TweetIDs。一个集中服务器将汇总这些结果并返回给用户。
7. 容错性
如果索引服务器宕机会怎么样？我们可以有每个服务器的次级副本，如果主服务器宕机，它可以在故障转移后接管。主服务器和次级服务器将有相同的索引副本。
如果主服务器和次级服务器同时宕机怎么办？我们必须分配一个新服务器并在其上重建相同的索引。我们怎么做呢？我们不知道这个服务器上保存了哪些单词/推文。如果我们使用的是'基于推文对象的分片'，暴力解决方案是遍历整个数据库，并使用我们的哈希函数过滤TweetIDs，以找出所有需要存储在这个服务器上的推文。这将是低效的，而且在服务器被重建的过程中，我们将无法从中提供任何查询，从而丢失一些用户应该看到的推文。
我们如何有效地检索推文和索引服务器之间的映射？我们必须建立一个反向索引，将所有的TweetID映射到它们的索引服务器。我们的索引构建器(Index-Builder)服务器可以保存这些信息。我们需要建立一个哈希表，其中'键'将是索引服务器编号，'值'将是一个包含在该索引服务器上保存的所有TweetIDs的哈希集。注意我们将所有的TweetIDs保存在一个哈希集中；这将使我们能够快速地从索引中添加/删除推文。所以现在，每当一个索引服务器需要重建自己，它可以简单地向索引构建器服务器请求它需要存储的所有推文，然后获取这些推文来构建索引。这种方法肯定会很快。我们还应该有一个索引构建器服务器的副本以实现容错。
8. 缓存
为了处理热门推文，我们可以在数据库前引入一个缓存。我们可以使用Memcached，它可以将所有这样的热门推文存储在内存中。应用服务器在查询后端数据库之前，可以快速检查缓存是否有该推文。根据客户的使用模式，我们可以调整我们需要多少缓存服务器。对于缓存驱逐策略，最近最少使用(LRU)似乎适合我们的系统。
9. 负载均衡
我们可以在系统的两个地方添加负载均衡层，1) 客户端和应用服务器之间，2) 应用服务器和后端服务器之间。最初，可以采用简单的轮询方式，该方式将传入请求均匀分布在后端服务器上。这种负载均衡很容易实现，且不会引入任何额外负担。这种方法的另一个好处是，负载均衡将从轮换中取出宕机的服务器，并停止向其发送任何流量。轮询负载均衡的问题在于它不会考虑服务器的负载。如果服务器过载或慢，负载均衡将不会停止向该服务器发送新的请求。为了处理这个问题，可以放置一个更智能的负载均衡解决方案，该解决方案定期查询后端服务器的负载并根据此调整流量。
10. 排名
如果我们想按社交图距离、人气、相关性等对搜索结果进行排名怎么办？
假设我们想根据人气对推文进行排名，比如一个推文获得了多少点赞或评论等。在这种情况下，我们的排名算法可以计算一个'人气数'（基于点赞数量等）并将其存储在索引中。每个分区都可以在将结果返回给汇总服务器之前，根据这个人气数对结果进行排序。汇总服务器将所有这些结果组合起来，根据人气数进行排序，并将最高的结果发送给用户。
推荐阅读
你好，我是拾叁，7年开发老司机、互联网两年外企5年。怼得过阿三老美，也被PR comments搞崩溃过。这些年我打过工，创过业，接过私活，也混过upwork。赚过钱也亏过钱。一路过来，给我最深的感受就是不管学什么，一定要不断学习。只要你能坚持下来，就很容易实现弯道超车！所以，不要问我现在干什么是否来得及。如果你还没什么方向，可以先关注我，这里会经常分享一些前沿资讯和编程知识，帮你积累弯道超车的资本。